/**
 * @Author Fizz Pu
 * @Date 2020/9/2 下午6:14
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.BitSet;
import java.util.List;

/**
 * 给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
 *
 * 示例 1:
 *
 * 输入: [1,3,4,2,2]
 * 输出: 2
 * 示例 2:
 *
 * 输入: [3,1,3,4,2]
 * 输出: 3
 * 说明：
 *
 * 不能更改原数组（假设数组是只读的）。
 * 只能使用额外的 O(1) 的空间。
 * 时间复杂度小于 O(n2) 。
 * 数组中只有一个重复的数字，但它可能不止重复出现一次。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-the-duplicate-number
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Lee287 {
    public static void main(String[] args) {
        System.out.println(findDuplicate(new int[]{1,2,2,3,4}));
        System.out.println(findDuplicate(new int[]{3,1,3,4,2}));
    }
    public static int findDuplicate(int[] nums) {
        // 联系今天学过的bitmap,节省内存
        BitSet bitSet = new BitSet(nums.length);
        int count = 0, len = nums.length;
        while (count < len){
            int value = nums[count];
            if(bitSet.get(value)){
                return value;
            }else {
                bitSet.set(value,true);
            }
            ++count;
        }
       return -1;
       // O(1)写法
        // 再次优化循环查找，采用二分查找
        /*Arrays.sort(nums); // 重复的连续
        int pre = nums[0], length = nums.length;
        for(int i = 1; i < length; ++i){
            if(nums[i] == pre)return pre;
            pre = nums[i];
        }
        return -1;*/
        }
    }
